#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution
{
public:
    Node *connect(Node *root)
    {
        queue<Node *> que;
        if (root != nullptr)
        {
            que.push(root);
        }
        while (!que.empty())
        {
            int length = que.size();
            Node *pre = nullptr;
            for (int i = 0; i < length; i++)
            {
                Node *node = que.front();
                que.pop();
                if (i == length - 1)
                {
                    node->next = nullptr;
                }
                if (i > 0)
                {
                    pre->next = node;
                }
                pre = node;

                if (node->left)
                {
                    que.push(node->left);
                }
                if (node->right)
                {
                    que.push(node->right);
                }
            }
        }
        return root;
    }
};

int main() {
    // 创建一个完美二叉树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // 调用 connect 函数
    Solution sol;
    root = sol.connect(root);

    // 验证 next 指针的连接
    // 第一层
    cout << "Node " << root->val << " -> Next: " 
         << (root->next ? to_string(root->next->val) : "nullptr") << endl;

    // 第二层
    cout << "Node " << root->left->val << " -> Next: " 
         << (root->left->next ? to_string(root->left->next->val) : "nullptr") << endl;
    cout << "Node " << root->right->val << " -> Next: " 
         << (root->right->next ? to_string(root->right->next->val) : "nullptr") << endl;

    // 第三层
    cout << "Node " << root->left->left->val << " -> Next: " 
         << (root->left->left->next ? to_string(root->left->left->next->val) : "nullptr") << endl;
    cout << "Node " << root->left->right->val << " -> Next: " 
         << (root->left->right->next ? to_string(root->left->right->next->val) : "nullptr") << endl;
    cout << "Node " << root->right->left->val << " -> Next: " 
         << (root->right->left->next ? to_string(root->right->left->next->val) : "nullptr") << endl;
    cout << "Node " << root->right->right->val << " -> Next: " 
         << (root->right->right->next ? to_string(root->right->right->next->val) : "nullptr") << endl;

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}